#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void generateSubsetHelper(const string &input, int start, int m, string &curStr, vector<string> &ans)
{
    if (curStr.size() == m) {
        ans.push_back(curStr);    
        return;
    }

    if (start == input.size())
        return;

    string::iterator iter;
    for (int i = start; i < input.size(); i++) {
        curStr += input[i];
        generateSubsetHelper(input, i+1, m, curStr, ans);
        iter = curStr.begin() + curStr.size()-1;
        curStr.erase(iter);
    }
}

vector<string> generateSubset(const string&input, int m)
{
    vector<string> ans; 
    string curStr;
    if (m > input.size()) {
        printf("Invalid input\n");    
        return ans;   //invalid input
    }

    generateSubsetHelper(input, 0, m, curStr, ans); 
    return ans; 
}

void printResult(const vector<string> &result)
{
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << " ";
    cout << endl;
}

int main(int argc, char **argv)
{
    string input;
    vector<string> result;

    cout << "-----------Test 1 ---------" << endl; 
    input  = "12345";
    result = generateSubset(input, 3);
    printResult(result); 
 
    cout << "-----------Test 2 ---------" << endl; 
    input  = "12345";
    result = generateSubset(input, 6);
    printResult(result); 

    cout << "-----------Test 3 ---------" << endl; 
    input  = "12345";
    result = generateSubset(input, 5);
    printResult(result); 

    return 0;
}
